package de.pass.ch.dijkstra;

import de.pass.ch.datastr.BinaryHeap;
import de.pass.ch.datastr.IntArrayGrowable;
import de.pass.ch.datastr.PQueueNode;
import de.pass.ch.datastr.PQueueNodeDynQuery;
import de.pass.ch.datastr.PQueueNodeLocalSearch;
import de.pass.ch.graph.IGraph;
import de.pass.ch.graph.node.CurrentNode;
import de.pass.ch.graph.node.INode;

public class AbstractDijkstra<P extends PQueueNode> {

	private static final boolean DEBUG = false;

	protected IGraph _graph;

	protected IntArrayGrowable[] _settledNodes;

	protected BinaryHeap<P>[] _pqueue;

	protected int _searchDirections;

	protected int _upperBound;

	protected int _via;

	public AbstractDijkstra(IGraph graph, IntArrayGrowable[] settledNodes,
			BinaryHeap<P>[] pqueue) {
		_graph = graph;
		_settledNodes = settledNodes;
		_pqueue = pqueue;
		_searchDirections = 2;
	}

	/**
	 * Returns the index of the corresponding pq element if the specified node
	 * is reached; returns 0, otherwise.
	 */
	public int isReached(int searchID, int vID) {
		return isReached(searchID, _graph.node(vID));
	}

	/**
	 * Returns the index of the corresponding pq element if the specified node
	 * is reached; returns 0, otherwise.
	 */
	public int isReached(int searchID, INode v) {
		int index = v.getPQElement();
		if (index == 0)
			return 0;
		if (_pqueue[searchID].isDummy(index))
			return 0;
		return index;
	}

	/**
	 * Returns the number of settled nodes in all search directions.
	 * 
	 * @return
	 */
	public int noOfSettledNodes() {
		if (_searchDirections == 2) {
			return _settledNodes[0].size() + _settledNodes[1].size();
		}
		return _settledNodes[0].size();
	}

	protected boolean deleteMin(int searchID, CurrentNode u) {
		u.index = _pqueue[searchID].deleteMin();
		return deleteElement(searchID, u);
	}

	/**
	 * Deletes an arbitrary element from the specified pqueue.
	 * 
	 * @see deleteElement(...)
	 * @return true iff 'successImpliesAbort' is turned on and both search
	 *         scopes have met
	 */
	protected boolean deleteArbitrary(int searchID) {
		CurrentNode u = new CurrentNode();
		u.index = _pqueue[searchID].deleteArbitrary();
		boolean result = deleteElement(searchID, u);

		return result;
	}

	/**
	 * Used as a subroutine by deleteMin and deleteArbitrary. Performs some
	 * necessary steps directly after a node has been deleted from a pqueue: the
	 * node is added to the list of settled nodes and (if applicable) it is
	 * checked whether both search scopes have met.
	 * 
	 * @see deleteMin(...)
	 * @see deleteArbitrary(...)
	 * @param searchID
	 *            the search direction (forwards/backwards)
	 * @param u
	 *            a reference to the CurrentNode object that contains the
	 *            minimum element: expects index; sets nodeID and dist
	 * @return true iff 'successImpliesAbort' is turned on and both search
	 *         scopes have met
	 */
	protected boolean deleteElement(int searchID, CurrentNode u) {
		// set nodeID and dist of the current node
		P data = pqData(searchID, u.index);
		u.nodeID = data.nodeID();
		u.dist = pqKey(searchID, u.index);

		// used for local search with hop-limit
		if (data instanceof PQueueNodeLocalSearch) {
			u.hops = data.hops();
		}

		// add current node to the list of settled nodes
		_settledNodes[searchID].add(u.nodeID);

		if (_searchDirections == 2) {
			// bidirectional search

			// check if both search scopes have met
			int index = isSettled(1 - searchID, u.nodeID);
			if (index != 0) {
				// The current node has been settled from the other direction as
				// well.
				// A new path has been found.
				int newDist = u.dist + pqKey(1 - searchID, index);
				// Check if the new path is shorter than the previously best
				// one.
				if (newDist < _upperBound) {
					_upperBound = newDist;
					_via = u.nodeID;
				}
				return true;
			}
		}
		return false;
	}

	protected int pqKey(int searchID, int index) {
		assert ((index > 0) && (index < _pqueue[searchID].elementsSize()));
		assert (!_pqueue[searchID].isDummy(index));

		return _pqueue[searchID].elementAt(index).key();
	}

	protected P pqData(int searchID, int index) {
		assert ((index > 0) && (index < _pqueue[searchID].elementsSize()));
		assert (!_pqueue[searchID].isDummy(index));

		return _pqueue[searchID].elementAt(index).data();
	}

	/**
	 * Processes all reached, but unsettled nodes for the given search
	 * direction. Invokes deleteArbitrary.
	 * 
	 * @see deleteArbitrary(...)
	 */
	protected void processUnsettledNodes(int searchID) {
		while (!_pqueue[searchID].empty()) {
			deleteArbitrary(searchID);
		}
	}

	/**
	 * Decreases the key of a given node if applicable.
	 * 
	 * @param searchID
	 *            the search direction (forwards/backwards)
	 * @param newDist
	 *            the new distance (key)
	 * @param v
	 *            the node whose key should be decreased
	 * @return the index of the element whose key has been decreased or 0 if the
	 *         key is not decreased.
	 */
	protected int decreaseKey(int searchID, int newDist, int v) {
		// retrieve the element that represents the given node v
		int index = _graph.node(v).getPQElement();
		int key = pqKey(searchID, index);

		// no improvement, no decreaseKey
		if (newDist >= key)
			return 0;

		_pqueue[searchID].decreaseKey(index, newDist);
		return index; // indicate that decreaseKey operation has been preformed
	}

	/**
	 * Returns the index of the corresponding pq element if the specified node
	 * is settled; returns 0, otherwise.
	 */
	protected int isSettled(int searchID, int vID) {
		int index = _graph.node(vID).getPQElement();
		if (index == 0)
			return 0;
		if (_pqueue[searchID].isDummy(index))
			return 0;

		// node IS reached ! Is it settled ?
		if (_pqueue[searchID].elementAt(index).hasBeenDeleted())
			return index;
		return 0;
	}

	protected void clearNodeVector(int searchID, int chunkSize) {
		for (int i = 0; i < _settledNodes[searchID].size(); i++) {
			_graph.node(_settledNodes[searchID].get(i)).setPQElement(0);
		}
		_settledNodes[searchID] = new IntArrayGrowable(chunkSize);
	}

	protected boolean checkClean() {
		if (!DEBUG) {
			return true; // deactivate this check
		}
		// This takes a lot of time.
		for (int u = 0; u < _graph.noOfNodes(); u++) {
			if (_graph.node(u).getPQElement() != 0)
				return false;
		}
		return true;
	}

	/**
	 * Inserts the given node with the given distance from the source node into
	 * the pqueue of the specified search direction.
	 * 
	 * @return the index of the pq element that represents the inserted node
	 */
	@SuppressWarnings("unchecked")
	protected int insert(int searchID, int dist, int nodeID, P _data) {
		int index = _graph.node(nodeID).getPQElement();
		if (index == 0) {
			index = _pqueue[searchID].insert(dist, _data);
			_graph.node(nodeID).setPQElement(index);
			if (_searchDirections == 2) {
				P dummy = null;
				if (_data instanceof PQueueNodeLocalSearch) {
					dummy = (P) new PQueueNodeLocalSearch();
				} else if (_data instanceof PQueueNodeDynQuery) {
					dummy = (P) new PQueueNodeDynQuery();
				} else {
					dummy = (P) new PQueueNode();
				}
				_pqueue[1 - searchID].insertDummy(dummy);
			}
		} else {
			_pqueue[searchID].insert(dist, index);
		}
		P data = pqData(searchID, index);
		data.init(nodeID);
		return index;
	}

}
